The present invention concerns in general the allocation to a plurality of elements of authorisations for access to a shared resource, so as best to adapt the sharing of the resource to the requirements of each element.
The invention applies notably to the sharing of a communication channel between communication means, for example the sharing of the passband of a radio channel between the mobile stations of a local wireless network.
In this context, the passband requirements of a mobile station vary considerably with time, notably according to the type of data to be transmitted (data, voice, image).
A predetermined fixed allocation of access authorisations would be not very effective since the traffic variations would not be taken into account.
Allocation of access authorisations must therefore be adapted to the requirements of each mobile station.
A known type of access authorisation allocation is a polling protocol. This technique makes it possible to achieve high throughputs, but with waiting times, or latencies, which may be large, that is to say a mobile station is liable to wait before accessing the resource, which prejudices the xe2x80x9cfluidityxe2x80x9d of the traffic.
Another access protocol is a contention, or conflict, protocol, in which a number of mobile stations are liable to transmit data simultaneously on the shared channel. This type of protocol therefore has a risk of collision. The latencies are generally small, but the throughputs are also lower than with a polling protocol.
Document EP-0 621 708 proposes notably an adaptive protocol for controlling access to a transmission medium which combines these two techniques. The protocol is based on a reservation scheme for the data traffic (polling) and a random access technique for the control and signalling traffic (contention).
A fixed time division frame structure consists of three periods. The first period is reserved exclusively for the transfer of data from the base station to the remote stations. The second period is used for the transfer of data from the remote stations to the base station.
The third period is the control channel, used for the transmission of reservation requests and data from the remote stations to the base station according to a random access contention mode.
The allocation of time intervals in the first two periods is made by the base station, according to the reservation requests made during the third period.
The risk of frame collision is not zero since, in the third period, the reservation request and data transmissions are carried out according to a random access mode. If it is wished to be free from the risk of collision, it is necessary to implement a collision detection mechanism, which is generally complex.
Furthermore, because of the three-period frame structure, a mobile station must wait until it has transmitted its reservation request before being capable of accessing the shared resource, in this case the second period.
The present invention aims to remedy the drawbacks of the prior art by providing a method and a device for allocation to a plurality of elements of authorisations for access to a shared resource, which allows throughputs comparable to those of the polling technique, while having latencies of the order of those of the contention technique.
To this end, the invention proposes a method for allocating, to a plurality of elements, authorisations for access to a shared resource, including the step of storing the address of elements capable of accessing the shared resource, characterised in that it includes the steps of:
determining, for the said plurality of elements, a number of authorisations for access to the resource, the said authorisations together forming an access cycle,
successively assigning each of the said authorisations to the elements during the said cycle, an access authorisation being assigned to an element according to at least the number of times the element under consideration accessed the resource during the preceding cycle, and
storing the number of times each element accesses the resource during the said cycle.
Correlatively, the invention concerns a device for allocating, to a plurality of elements, authorisations for access to a shared resource, having a memory means for storing the address of elements capable of accessing the shared resource, characterised in that it has:
means for determining, for the said plurality of elements, a number of authorisations for access to the resource, the said number of authorisations forming an access cycle,
means for successively assigning each of the said authorisations to the elements, during the said cycle, an access authorisation being assigned to an element according to at least the number of times the element under consideration accessed the resource during the preceding cycle, and
means for storing the number of times each element accesses the resource during the said cycle.
The method and the device apply particularly where the elements are data communication means, and the shared resource is a communication channel. The plurality of elements considered is the set of elements which are capable of accessing the shared resource.
The method and the device according to the invention have not only the advantage of solving the technical problem described above, but also that of avoiding any risk of collision, since they are based on a polling protocol.
The invention also concerns a device for allocating, to a plurality of elements, authorisations for access to a shared resource, adapted to cooperate with a memory means for storing the address of elements capable of accessing the shared resource, characterised in that it has logic means having:
means for determining, for the said plurality of elements, a number of authorisations for access to the resource, the said authorisations together forming an access cycle,
means for successively assigning each of the said authorisations to the elements, during the said cycle, an access authorisation being assigned to an element according to at least the number of times the element under consideration accessed the resource during the preceding cycle, and
means for cooperating with memory means adapted to store the number of times each element accesses the resource during the said cycle.
According to preferred embodiments, possibly combined:
the number of access authorisations is determined according to the sum of the number of accesses to the shared resource which each element made during the preceding cycle,
the number of access authorisations depends on the sum of the number of accesses which each element had still to make at the end of the preceding cycle.
Advantageously, the number of access authorisations is limited at a lower value by a value dependent on the number of elements capable of accessing the resource. Thus the cycle has a sufficient length so that all the elements can access the shared resource during one cycle.
According to a first preferred embodiment, the number of access authorisations is weighted by a weighting factor which depends on the sum of the number of accesses to the shared resource which each element made during the preceding cycle.
According to a second preferred embodiment, the number of access authorisations is weighted by a weighting factor which depends on the sum of the number of accesses to the shared resource which each element made during the preceding cycle, and the number of accesses which each element had still to make at the end of the preceding cycle.
Advantageously, determination of the number of access authorisations is carried out between two cycles, which makes it possible to regularly adapt the length of the cycle to the requirements of the elements.
In order to simplify the implementation, the number of authorisations for access to the resource may be predetermined.
In general, the assigning of an access authorisation includes comparing the elements according to a criterion which depends on the number of authorisations previously assigned to each element during the said cycle, and the number of times each element accessed the resource during the preceding cycle.
According to a first preferred embodiment, the assigning of each access authorisation includes:
calculating, for each element, the ratio between the number of access authorisations previously assigned to the said element during the current cycle, and the number of accesses to the shared resource which the said element made during the preceding cycle,
comparing the ratios calculated previously,
assigning the access authorisation to the element for which the ratio is the smallest.
According to a second preferred embodiment, the assigning of each access authorisation includes:
calculating, for each element, the ratio between the number of access authorisations previously assigned to the said element during the current cycle, and the sum of the number of accesses to the shared resource which the said element made during the preceding cycle and the number of accesses which the said element had still to make at the end of the preceding cycle,
comparing the ratios calculated previously,
assigning the access authorisation to the element for which the ratio is the smallest.
According to a third preferred embodiment, the assigning of each access authorisation includes:
calculating, for one of the elements, a first ratio between the number of access authorisations previously assigned to the said element during the current cycle, and the number of accesses to the shared resource which the said element made during the preceding cycle,
calculating, for the said element, a second ratio between the number of access authorisations previously assigned to the elements of a group not including the said element, during the current cycle, and the number of accesses to the shared resource which the said elements of the group made during the preceding cycle,
comparing the first and second ratios calculated previously,
assigning the access authorisation to the said element if the first ratio is less than the second ratio or, if not, reiterating the preceding steps for another element selected from the group.
According to a fourth embodiment, the assigning of each access authorisation includes:
calculating, for one of the elements, a first ratio between the number of access authorisations previously assigned to the said element during the current cycle, and the sum of the number of accesses to the shared resource which the said element made during the preceding cycle and the number of accesses which the said element had still to make at the end of the preceding cycle,
calculating, for the said element, a second ratio between the number of access authorisations previously assigned to the elements of a group not including the said element, during the current cycle, and the difference between the number of accesses to the shared resource which the said elements of the group made during the preceding cycle, and the number of accesses which the said element had still to make at the end of the preceding cycle,
comparing the first and second ratios calculated previously,
assigning the access authorisation to the said element if the first ratio is less than the second ratio or, if not, reiterating the preceding steps for another element selected from the group.
The group includes elements which previously accessed the resource during the preceding cycle a number of times fewer than that of the said element.
The calculations necessary for assigning access authorisations are preferably distributed over the whole of the current cycle; thus there is no calculation time between two consecutive cycles.
According to other characteristics, the method also includes the steps of
broadcasting invitations to declare oneself to the elements,
receiving a reply from an element capable of accessing the shared resource and of which the address is not stored, and
storing the address of the said element.
The method also includes the step of
deleting from the memory the address of elements for which the number of accesses to the shared resource is zero for a specific number of consecutive cycles.
The device according to the invention has corresponding means; these characteristics make it possible to add or remove elements of the set of elements capable of accessing the shared resource.